#include"BinaryTree.h"
BTNode* BuyBinaryNode(char x)
{
	BTNode* Node = (BTNode*)malloc(sizeof(BTNode));
	if (Node == NULL)
	{
		perror("malloc");
		return NULL;
	}
	Node->_data = x;
	Node->_left = Node->_right = NULL;
	return Node;
}
BTNode* _BinaryTreeCreate(int* i,BTDataType* a,int n)
{
	if (a[*i] == '#')
	{
		(*i)++;
		return NULL;
	}
	BTNode* Node = (BTNode*)malloc(sizeof(BTNode));
	if (Node == NULL)
	{
		return NULL;
	}
	Node->_data = a[(*i)++];
	Node->_left = _BinaryTreeCreate(i, a,n);
	Node->_right = _BinaryTreeCreate(i, a,n);
	return Node;
}
BTNode* BinaryTreeCreate(BTDataType* a, int n)
{
	int i = 0;
	return _BinaryTreeCreate(&i, a,n);
}

void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&(*root)->_left);
	BinaryTreeDestory(&(*root)->_right);
	free(*root);
	*root = NULL;
}
void css(BTNode* root, int* size)
{
	if (root == NULL)
	{
		return;
	}
	(*size)++;
	css(root->_left,size);
	css(root->_right,size);
}
int BinaryTreeSize(BTNode* root)
{
	//int size = 0;
	//css(root, &size);
	if (root == NULL)
	{
		return 0;
	}
	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->_left == NULL && root->_right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->_left)+BinaryTreeLeafSize(root->_right);
}

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}

	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
	return 0;
}

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->_data == x)
	{
		return root;
	}
	if (BinaryTreeFind(root->_left, x) != NULL)
	{
		return BinaryTreeFind(root->_left, x);
	}
	if (BinaryTreeFind(root->_right, x) != NULL)
	{
		BinaryTreeFind(root->_right, x);
	}
}

